import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

class MajorityChecker {

    Map<Integer, Integer>[] prefixInfo;

    public MajorityChecker(int[] arr) {
        prefixInfo = new Map[arr.length];
        prefixInfo[0] = new TreeMap<>();
        prefixInfo[0].put(arr[0], 1);
        for (int i = 1; i < arr.length; i++) {
            prefixInfo[i] = new TreeMap<>(prefixInfo[i - 1]);
            prefixInfo[i].put(arr[i], prefixInfo[i].getOrDefault(arr[i], 0) + 1);
        }
    }

    public int query(int left, int right, int threshold) {
        Map<Integer, Integer> countInfo = new TreeMap<>(prefixInfo[right]);
        if(left != 0){
            Map<Integer, Integer> subInfo = prefixInfo[left - 1];
            for (Map.Entry<Integer, Integer> et : countInfo.entrySet()) {
                et.setValue(et.getValue() - subInfo.getOrDefault(et.getKey(), 0));
            }
        }
        Integer mostNum = null, mostCount = 0;
        for (Map.Entry<Integer, Integer> et : countInfo.entrySet()) {
            if(et.getValue() > mostCount){
                mostNum = et.getKey();
                mostCount = et.getValue();
            }
        }
        return mostCount >= threshold ? mostNum:-1;
    }

    public static void main(String[] args) {
        MajorityChecker mc = new MajorityChecker(new int[]{1,1,2,2,1,1});
        System.out.println(mc.query(0,5,4));
    }
}
